package lcr;

public class Test0101 {

    public static void main(String[] args) {
        new Solution0101_1().canPartition(new int[]{14,9,8,4,3,2});
    }
}

class Solution0101_1 {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num : nums) sum += num;
        if ((sum&1)==1) return false;
        int target = sum>>1;

        boolean[] dp = new boolean[target+1];
        dp[0]=true;
        for (int num : nums) {
            for (int i = target; i >= num; i--)
                dp[i]|=dp[i-num];
            if (dp[target]) return true;
        }

        return dp[target];
    }
}
